The present invention relates to bandwidth reservation in high speed packet networks and more particularly to a method and system for sharing reserved bandwidth between several virtual logical connections issuing from a same port attaching external devices.
HIGH SPEED PACKET SWITCHING NETWORKS
Data transmission is now evolving with a specific focus on applications and by integrating a fundamental shift in the customer traffic profile. Driven by the growth of workstations, the local area networks interconnection, the distributed processing between workstations and super computers, the new applications and the integration of various and often conflicting structuresxe2x80x94hierarchical versus peer to peer, wide versus local area networks, voice versus dataxe2x80x94the data profile has become more bandwidth consuming, bursting, non-deterministic and requires more connectivity. Based on the above, there is strong requirement for supporting distributed computing applications across high speed networks that can carry local area network communications, voice, video and traffic among channel attached hosts, business, engineering workstations, terminals, and small to intermediate file servers. This vision of a high speed multi-protocol network is the driver for the emergence of fast packet switching networks architectures in which data, voice, and video information is digitally encoded, chopped into small packets and transmitted through a common set of nodes and links.
An efficient transport of mixed traffic streams on very high speed lines means for these new network architecture a set of requirements in term of performance and resource consumption which can be summarized as follows:
a very high throughput and a very short packet processing time.
a very large flexibility to support a wide range of connectivity options,
an efficient flow and congestion control.
THROUGHPUT AND PROCESSING TIME
One of the key requirement of high speed packet switching networks is to reduce the end to end delay in order to satisfy real-time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes and the fundamental challenge for high speed networks is to minimize the processing time and to take full advantage of the high speed/low error rate technologies, most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end to end basis. The flow control and particularly the path selection and bandwidth management processes are managed by the access points of the network which reduces both the awareness and the function of the intermediate nodes.
CONNECTIVITY
In high speed networks, the nodes must provide a total connectivity. This includes attachment of the user""s devices, regardless of vendor or protocol, and the ability to have the end user communicated with any other device. The network must support any type of traffic including data, voice, video, fax, graphic or image. Nodes must be able to take advantage of all common carrier facilities and to be adaptable to a plurality of protocols. All needed conversions must be automatic and transparent to the end user.
CONGESTION AND FLOW CONTROL
Communication networks have at their disposal limited resources to ensure an efficient packets transmission. An efficient bandwidth management is essential to take full advantage of a high speed network. While transmission costs per byte continue to drop year after year, transmission costs are likely to continue to represent the major expense of operating future telecommunication networks as the demand for bandwidth increases. Thus considerable efforts have been spent on designing flow and congestion control processes, bandwidth reservation mechanisms, routing algorithms to manage the network bandwidth. An ideal network should be able to transmit an useful traffic directly proportional to the traffic offered to the network and this as far as the maximum transmission capacity is reached. Beyond this limit, the network should operate at its maximum capacity whatever the demand is.
DEPENDENT CONNECTIONS
Private Network (PN) and Value-Added Network (VAN) service providers usually build their networks upon carrier transmission facilities. The expense for carrier transmission facilities represents an important part (about 30% to 60%) of the PN""s or VAN""s total operating expense. As such, their profits are directly related to their ability to minimize monthly transmission expenses while continually meeting their customers"" end-to-end communications needs. Nodal equipment that can utilize the transmission facilities more efficiently than traditional carrier systems are typically selected by PNs and VANs.
Today, the replacement of traditional Time Division Multiplex (TDM) equipment by high speed packet switching equipment has significantly reduced the amount of transmission facilities needed in a Private Network (PN) or in a Value-Added Network (VAN). But much like TDM networks, packet switching networks approach falls short of reducing the amount of transmission facilities (transmission trunks) required in the backbone network. The reason for this is that most packet switching network architectures assume that all incoming traffic streams are xe2x80x9cindependentxe2x80x9d with respect to each other. That is, any customer device attached to the network can provide incoming traffic to the network at any instant of time. This is not true for logical virtual connections as in the case of Frame Relay (FR), Local Area Network (LAN), or Asynchronous Transfer Mode (ATM) traffic. In fact, the logical connections of a FR, LAN or ATM attached device must consider the traffic sources from all logical virtual connections established on a given physical port as xe2x80x9cdependentxe2x80x9d. When a logical virtual connection is bursting a traffic stream, no other logical virtual connection can burst at the same time.
A network architecture such as the NBBS architecture described in IBM""s publication entitled xe2x80x9cNetworking Broadband Services (NBBS)xe2x80x94Architecture Tutorialxe2x80x9d IBM ITSC, June 1995 GG24-4486-00, reserves for virtual Frame Relay (FR) connections more bandwidth than necessary on the backbone network. This occurs because NBBS considers each Data Link Connection Identifier (DLCI) (refer to Frame Relay core aspects ANSI T1.618-1991 and ITU-T Q.922 Annex A) as an independent traffic source, and reserves bandwidth on the backbone network accordingly. FIG. 4 illustrates virtual Frame Relay/ATM (FR/ATM) connections between four nodes, named A, B, C, and D. Digital Terminal Equipment are connected to ports in these nodes by means of access links. From the Frame Relay/ATM port in origin node A, three virtual logical connections are established respectively towards destination ports B, C and D. Assuming in this example that the traffic is the same for each connection:
R (Access Rate)=2 Mbps,
CIR (Committed Information Rate)=300 kbps,
Bc (Burst Committed)=4 kbytes
the bandwidth reserved on a trunk with a multiplexing buffer of 64 kbytes in order to guarantee a packet loss probability of xcex5=5xc3x9710xe2x88x928, is approximately 700 kbps for each connection.
The bandwidth reserved by the NBBS architecture on a trunk to support a connection is defined according to the following equation:       c    ^    =            R      ⁢              xe2x80x83            ⁢                        y          -          X          +                                                                      [                                      y                    -                    X                                    ]                                2                            +                              4                ⁢                X                ⁢                                  xe2x80x83                                ⁢                ρ                ⁢                                  xe2x80x83                                ⁢                y                                                              2          ⁢          y                      ≃          700      ⁢              xe2x80x83            ⁢      kbps      
where:   "AutoLeftMatch"                                          X            =                          xe2x80x83                        ⁢                                          64000                ⁢                                  xe2x80x83                                ⁢                bytes                xc3x97                8                            =                              512000                ⁢                                  xe2x80x83                                ⁢                bits                                              ⁢                      xe2x80x83                                                                    xe2x80x83                    ⁢                                    (                              size                ⁢                                  xe2x80x83                                ⁢                of                ⁢                                  xe2x80x83                                ⁢                the                ⁢                                  xe2x80x83                                ⁢                buffer                ⁢                                  xe2x80x83                                ⁢                where                ⁢                                  xe2x80x83                                ⁢                packets                ⁢                                  xe2x80x83                                ⁢                are                ⁢                                  xe2x80x83                                ⁢                queued                            )                        ,                                                                    b            =                          xe2x80x83                        ⁢                                                            B                  c                                R                            =                                                                    4                    ⁢                                          xe2x80x83                                        ⁢                    kbytes                    xc3x97                    8                                                        2048                    ⁢                                          xe2x80x83                                        ⁢                    kbps                                                  =                                  0.16                  ⁢                                      xe2x80x83                                    ⁢                  ms                  ⁢                                      xe2x80x83                                    ⁢                                      (                                          average                      ⁢                                              xe2x80x83                                            ⁢                      burstiness                                        )                                                                                ,                                                          y            =                          xe2x80x83                        ⁢                                          ln                ⁡                                  (                                      1                    /                    ϵ                                    )                                            ⁢                              b                ⁡                                  (                                      1                    -                    ρ                                    )                                            ⁢              R                                ,                      xe2x80x83                    ⁢          and                                              ρ          =                      xe2x80x83                    ⁢                                    CIR              /              R                        =                                          300                ⁢                                  xe2x80x83                                ⁢                kbps                ⁢                                  /                                ⁢                2048                ⁢                                  xe2x80x83                                ⁢                kbps                            ≃                              0.15                .                                                        
Therefore, the bandwidth reserved on each trunk is given in the table below:
This example shows that the total bandwidth that should be reserved for 3 connections on Trunk 1 is about 2100 kbps (3 connections at 700 kbps). The value is higher than the access rate (R=2 Mbps) of the physical port (FR/ATM port A) supporting these connections. This situation is clearly not acceptable. In the simple case where a physical port is fully loaded with 7 connections (7xc3x97300 kbps=2 Mbps) and where all the connections issuing from said port are transmitted over a single trunk (Trunk 1), the bandwidth requirement is about 4.9 Mbps (7xc3x97700 kbps), while it is clear that the 2 Mbps stream produced by said port can be transmitted over a 2 Mbps trunk. Again, this occurs because NBBS considers each connection as an independent traffic source and supposes that all connections can be bursty at the same time. Considering this worst case, NBBS reserves 4.9 Mbps to be sure to be able to transmit 2 Mbps.
NON PUBLISHED U.S. PATENT APPLICATION SER. NO. 97,131
Non published U.S. patent application Ser. No 97,131 (IBM""s reference FR 9 95 035) entitled xe2x80x9cMethod and System for Sharing Reserved Bandwidth Between Several Dependent Connections in High Speed Packet Switching Networksxe2x80x9d (Galand et al.) discloses a Dependent Connection Bandwidth Management method and system for taking advantage of the property of dependent virtual logical connections in a packet switching communication network comprising a plurality of nodes interconnected with transmission trunks. More particularly, the object of this application is to share the reserved bandwidth between several connections issuing from a same physical access port. An aggregate bandwidth is reserved for all connections issuing from the same physical port, this aggregate bandwidth is defined as being less than the sum of the bandwidth reserved for each connection considered individually. In a network where the bandwidth reserved for an individual connection is equal to the equivalent capacity of the connection, the aggregate bandwidth reserved for all dependent connections is defined as a function of:
the mean bit rate of the aggregation of connections issued from said port, and
the mean burst duration of the aggregation of connections issued from said port.
The Dependent Connection Bandwidth Management process as described in the specifications is based on:
1. an accounting per port of all connections established on every link in the network.
2. a modification of the Path Selection algorithm in access nodes,
3. an insertion of additional fields in the connection set-up message, and
4. a modification of the Transit Connection Manager (TCM) algorithm within Transit nodes.
This solution reduces the bandwidth required for the dependent connections in the backbone network, while still guaranteeing an end-to-end quality-of-service. However, this solution is complex to implement and resource consuming because based on a set of algorithms implemented in both access nodes (in particular in the Path Selection), and transit nodes (in the Transit Connection Managers (TCM)).
The object of the present application is to provide an improved method and system for saving bandwidth on links taking advantage of the property of dependent connections while limiting the resources required for establishing connections in both access and transit nodes.
It is another object of the present application to reduce the processing time necessary to establish connections and in particular the time for selecting a routing path. It is another object of the present application to make easier the migration of existing. networks and the coexistence of the present invention with other networks architectures.
According to the present invention dependent connections are managed:
independently of the Path Selection algorithm, and
only in access nodes.
At each request for establishing a connection i from an origin node to a destination node, the dependent connection management process:
selects for connection i a routing path comprising one or a plurality of links from the origin node to the destination node;
identifies on the selected path all consecutive links starting from the origin node and shared with another connection issuing from the same physical port;
reserves on each link of these identified consecutive links an aggregate bandwidth for all connections issuing from the same physical port, said aggregate bandwidth being less than the sum of the bandwidth reserved for each connection considered individually.
Two tables are defined for each port p:
a Dependent Connection Table DCTp comprising for each link in the network, information required to manage the bandwidth and the dependency of connections issuing from the port;
a Path Table PTp with the links comprised in the selected routing path of each connection issuing from the port.